package top.fengleifeng.question;

import top.fengleifeng.util.Constants;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * @author : fengelfeing
 * @Package : top.fengleifeng.question
 * @Description:
 * @Date: 2020年10月29日7:51 下午
 */
public class Num18四数之和 {
    //四指针做法 a,b,c,d a
    class Solution {
        public List<List<Integer>> fourSum(int[] nums, int target) {
            List<List<Integer>> result = new LinkedList<>();
            Map<String, String> check = new HashMap<>();
            int length = nums.length;
            Arrays.sort(nums);
            for (int i = 0; i < length - 3; i++) {
                int a = nums[i];
                int oneTarget = target - a;
                for (int j = i + 1; j < length - 2; j++) {
                    int b = nums[j];
                    //然后进行处理
                    int twoTarget = oneTarget - b;
                    int cIndex = j + 1;
                    int dIndex = length - 1;
                    int c = nums[cIndex];
                    int d = nums[dIndex];
                    while (cIndex < dIndex) {
                        int now = c + d;
                        if (now == twoTarget) {
                            String checkstr = "" + a + b + c + d;
                            if (check.containsKey(checkstr)) {
                                c = nums[++cIndex];
                            } else {
                                List<Integer> one = new ArrayList<>(4);
                                one.add(a);
                                one.add(b);
                                one.add(c);
                                one.add(d);
                                result.add(one);
                                check.put(checkstr, checkstr);
                            }
                        } else if (now > twoTarget) {
                            d = nums[--dIndex];;
                        } else {
                            c = nums[++cIndex];;
                        }
                    }
                }
            }
            return result;
        }
    }

    public static void main(String[] args) {
//        int[] ints = {1, 0, -1, 0, -2, 2};
//        int i = 0;
        int[] ints = {0, 0, 0, 0};
        int i = 0;
        List<List<Integer>> lists = new Num18四数之和().new Solution().fourSum(ints, i);
        Constants.pringtLinkedList(lists);
    }
}
